{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways to Earn Points"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: waysToReachTarget"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #获得分数的方法数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>考试中有 <code>n</code> 种类型的题目。给你一个整数 <code>target</code> 和一个下标从 <strong>0</strong> 开始的二维整数数组 <code>types</code> ，其中 <code>types[i] = [count<sub>i</sub>, marks<sub>i</sub>] </code>表示第 <code>i</code> 种类型的题目有 <code>count<sub>i</sub></code> 道，每道题目对应 <code>marks<sub>i</sub></code> 分。</p>\n",
    "\n",
    "<p>返回你在考试中恰好得到 <code>target</code> 分的方法数。由于答案可能很大，结果需要对 <code>10<sup>9</sup> +7</code> 取余。</p>\n",
    "\n",
    "<p><strong>注意</strong>，同类型题目无法区分。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比如说，如果有 <code>3</code> 道同类型题目，那么解答第 <code>1</code> 和第 <code>2</code> 道题目与解答第 <code>1</code> 和第 <code>3</code> 道题目或者第 <code>2</code> 和第 <code>3</code> 道题目是相同的。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>target = 6, types = [[6,1],[3,2],[2,3]]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>要获得 6 分，你可以选择以下七种方法之一：\n",
    "- 解决 6 道第 0 种类型的题目：1 + 1 + 1 + 1 + 1 + 1 = 6\n",
    "- 解决 4 道第 0 种类型的题目和 1 道第 1 种类型的题目：1 + 1 + 1 + 1 + 2 = 6\n",
    "- 解决 2 道第 0 种类型的题目和 2 道第 1 种类型的题目：1 + 1 + 2 + 2 = 6\n",
    "- 解决 3 道第 0 种类型的题目和 1 道第 2 种类型的题目：1 + 1 + 1 + 3 = 6\n",
    "- 解决 1 道第 0 种类型的题目、1 道第 1 种类型的题目和 1 道第 2 种类型的题目：1 + 2 + 3 = 6\n",
    "- 解决 3 道第 1 种类型的题目：2 + 2 + 2 = 6\n",
    "- 解决 2 道第 2 种类型的题目：3 + 3 = 6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>target = 5, types = [[50,1],[50,2],[50,5]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>要获得 5 分，你可以选择以下四种方法之一：\n",
    "- 解决 5 道第 0 种类型的题目：1 + 1 + 1 + 1 + 1 = 5\n",
    "- 解决 3 道第 0 种类型的题目和 1 道第 1 种类型的题目：1 + 1 + 1 + 2 = 5\n",
    "- 解决 1 道第 0 种类型的题目和 2 道第 1 种类型的题目：1 + 2 + 2 = 5\n",
    "- 解决 1 道第 2 种类型的题目：5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>target = 18, types = [[6,1],[3,2],[2,3]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>只有回答所有题目才能获得 18 分。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= target &lt;= 1000</code></li>\n",
    "\t<li><code>n == types.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 50</code></li>\n",
    "\t<li><code>types[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= count<sub>i</sub>, marks<sub>i</sub> &lt;= 50</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-to-earn-points](https://leetcode.cn/problems/number-of-ways-to-earn-points/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-to-earn-points](https://leetcode.cn/problems/number-of-ways-to-earn-points/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6\\n[[6,1],[3,2],[2,3]]', '5\\n[[50,1],[50,2],[50,5]]', '18\\n[[6,1],[3,2],[2,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        states = [0]*(target+1)\n",
    "        states1 = [0]*(target+1)\n",
    "        states[0] = 1\n",
    "        M = 10**9+7\n",
    "        for count, mark in types:\n",
    "            for score in range(target+1):\n",
    "                _min = score - mark * min(score // mark, count)\n",
    "                v = states[score] + (states1[score-mark]  if score >= mark else 0)\n",
    "                if _min >= mark:\n",
    "                    v -= states[_min - mark]\n",
    "                states1[score] = v % M\n",
    "                #sum(states[s] for s in range(_min, score+1, mark))\n",
    "            states1, states = states, states1\n",
    "        return states[-1]\n",
    "\n",
    "        # R[ty][t] = R[ty-1][s] if t - s  = m\n",
    "        # "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        n = len(types)\n",
    "        f = [[0] * (target + 1) for _ in range(n+1)]\n",
    "        f[0][0] = 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            c, v = types[i-1][0], types[i-1][1]\n",
    "            for j in range(target+1):\n",
    "                maxc = min(c, j // v)\n",
    "                for k in range(maxc + 1):\n",
    "                    f[i][j] += f[i-1][j - k * v]\n",
    "            f[i][j] %= (10 ** 9 + 7)\n",
    "        \n",
    "        return f[n][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        mod = 10**9+7\n",
    "        n=len(types)\n",
    "        dp = [[0]*(target+1) for _ in range(n+1)]\n",
    "        dp[0][0]=1\n",
    "        for i in range(1,n+1):\n",
    "            count,score = types[i-1]\n",
    "            \n",
    "            for j in range(target+1):\n",
    "                for k in range(count+1):\n",
    "                    if j>=score*k:\n",
    "                        dp[i][j] +=(dp[i-1][j-score*k])\n",
    "                    dp[i][j] =dp[i][j]%mod\n",
    "        print(dp)\n",
    "        return dp[-1][-1]\n",
    "        \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        #一维dp数组\n",
    "        # MOD = 10 ** 9 + 7\n",
    "        # f = [1] + [0] * target\n",
    "        # for count, marks in types:\n",
    "        #     for j in range(target, 0, -1):\n",
    "        #         for k in range(1, min(count, j // marks) + 1):\n",
    "        #             f[j] += f[j - k * marks]\n",
    "        #         f[j] %= MOD\n",
    "        # return f[-1]\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [[0 for _ in range(target+1)] for _ in range(len(types))]\n",
    "        dp[0][0] =1\n",
    "        for i in range(types[0][0]):\n",
    "            if types[0][1]*(i+1) < len(dp[0]):\n",
    "                dp[0][types[0][1]*(i+1)] = 1\n",
    "        for i in range(1,len(types)):\n",
    "            print(i)\n",
    "            for j in range(target+1):\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "                for k in range(1,min(types[i][0],j//types[i][1])+1):\n",
    "                    dp[i][j] += dp[i-1][j-k*types[i][1]]\n",
    "        print(dp)\n",
    "        return dp[-1][-1] % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        mem = [[-1]*1007 for _ in range(55)]\n",
    "        n = len(types)\n",
    "        mod = int(1e9 + 7)\n",
    "        def dfs(score, i):\n",
    "            if score > target:\n",
    "                return 0\n",
    "            if score == target:\n",
    "                return 1\n",
    "            if i == n:\n",
    "                return 0\n",
    "            if mem[i][score] != -1:\n",
    "                return mem[i][score]\n",
    "            count, marks = types[i]\n",
    "            res = 0\n",
    "            for j in range(count+1):\n",
    "                res = (res + dfs(score + marks*j, i + 1)) % mod\n",
    "            mem[i][score] = res\n",
    "            return res\n",
    "        return dfs(0, 0) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        mem = [[-1]*1007 for _ in range(55)]\n",
    "        n = len(types)\n",
    "        mod = int(1e9 + 7)\n",
    "        def dfs(score, i):\n",
    "            if score == 0:\n",
    "                return 1\n",
    "            if score < 0:\n",
    "                return 0\n",
    "            if i == n:\n",
    "                return 0\n",
    "            if mem[i][score] != -1:\n",
    "                return mem[i][score]\n",
    "            count, marks = types[i]\n",
    "            res = 0\n",
    "            for j in range(count+1):\n",
    "                res = (res + dfs(score - marks*j, i + 1)) % mod\n",
    "            mem[i][score] = res\n",
    "            return res\n",
    "        return dfs(target, 0) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        self.mod = int(1e9 + 7)\n",
    "        return self.process(target, types, 0, 0, {})\n",
    "\n",
    "    def process(self, target, types, i, curr, table):\n",
    "        n = len(types)\n",
    "        if i == n:\n",
    "            if curr == target:\n",
    "                return 1\n",
    "            return 0\n",
    "        if (i, curr) not in table:\n",
    "            val = 0\n",
    "            for j in range(types[i][0] + 1):\n",
    "                newCurr = curr + j * types[i][1]\n",
    "                if newCurr > target:\n",
    "                    break\n",
    "                val = (val + self.process(target, types, i + 1, newCurr, table)) % self.mod\n",
    "            table[(i, curr)] = val\n",
    "        return table[(i, curr)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        dp = np.zeros([1, target + 1], dtype=object)\n",
    "        dp[0][0] = 1\n",
    "        for c, s in types:\n",
    "            dp = np.tile(dp, [c + 1, 1])\n",
    "            for j in range(s, target + 1):\n",
    "                for i in range(1, c + 1):\n",
    "                    dp[i][j] += dp[i - 1][j - s]\n",
    "            dp = dp[[-1]]\n",
    "        return dp[0][-1] % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "# 考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维整数数组 types ，其中 types[i] = [counti, marksi] 表示第 i 种类型的题目有 counti 道，每道题目对应 marksi 分。\n",
    "\n",
    "# 返回你在考试中恰好得到 target 分的方法数。由于答案可能很大，结果需要对 109 +7 取余。\n",
    "\n",
    "# 注意，同类型题目无法区分。\n",
    "\n",
    "# 比如说，如果有 3 道同类型题目，那么解答第 1 和第 2 道题目与解答第 1 和第 3 道题目或者第 2 和第 3 道题目是相同的。\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(index: int, remain: int) -> int:\n",
    "            if remain < 0:\n",
    "                return 0\n",
    "            if index == n:\n",
    "                return 1 if remain == 0 else 0\n",
    "            # 做几道题\n",
    "            res = 0\n",
    "            for i in range(types[index][0] + 1):\n",
    "                res += dfs(index + 1, remain - i * types[index][1])\n",
    "                res %= MOD\n",
    "            return res\n",
    "\n",
    "        n = len(types)\n",
    "        res = dfs(0, target)\n",
    "        dfs.cache_clear()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, nums: List[List[int]]) -> int:\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(i, c):\n",
    "            if i < 0:\n",
    "                return 0 if c != 0 else 1\n",
    "            if c < nums[i][1]:\n",
    "                return dfs(i - 1, c)\n",
    "            k = c // nums[i][1]\n",
    "            k = min(k, nums[i][0])\n",
    "            return sum([dfs(i - 1, c - nums[i][1] * j) for j in range(k + 1)]) % int(1e9 + 7)\n",
    "        return dfs(len(nums) - 1, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from functools import lru_cache\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def dfs(mask):\n",
    "            target, pos = mask//100, mask%100\n",
    "            if target == 0: return 1\n",
    "            if target < 0 or pos == len(types): return 0\n",
    "            ans = 0\n",
    "            for i in range(types[pos][0]+1):\n",
    "                t = target-i*types[pos][1]\n",
    "                if t<0: break\n",
    "                ans += dfs(t*100 + pos+1)\n",
    "            return ans % (10**9 +7)\n",
    "\n",
    "        return dfs(target*100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        n = len(types)\n",
    "        types += [[0, inf]]\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        dp = [[[0 for k in range(50)] for j in range(target)] for i in range(n+1)]\n",
    "        \n",
    "\n",
    "        @cache\n",
    "        def dfs(i, t):\n",
    "            if t < 0:\n",
    "                return 0\n",
    "            if i == n:\n",
    "                return 1 if t == 0 else 0\n",
    "            if types[i][1] > t:\n",
    "                return dfs(i+1, t) % mod\n",
    "            res = sum([dfs(i+1, t-j*types[i][1]) for j in range(types[i][0] + 1)])\n",
    "            return res % mod\n",
    "\n",
    "        return dfs(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        n = len(types)\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            if j == 0:\n",
    "                return 1\n",
    "            if j < 0:\n",
    "                return 0\n",
    "            if i == -1:\n",
    "                return 0\n",
    "            return sum(f(i-1, j-x) for x in range(types[i][0]*types[i][1], -1, -types[i][1]))%MOD\n",
    "        return f(n-1, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        '''\n",
    "        #递归，会超时\n",
    "        if len(types) == 1:\n",
    "            if target % types[0][1] == 0 and types[0][0] * types[0][1] >= target: return 1\n",
    "            else: return 0\n",
    "        else:\n",
    "            cnt = 0\n",
    "            for i in range(types[0][0] + 1):\n",
    "                target_ = target - i * types[0][1]\n",
    "                if target_ == 0:\n",
    "                    cnt += 1\n",
    "                    break\n",
    "                elif target_ > 0:\n",
    "                    cnt += self.waysToReachTarget(target_, types[1:])\n",
    "                else:\n",
    "                    break\n",
    "            return cnt\n",
    "        '''\n",
    "\n",
    "        # 递归\n",
    "        lst, dct = [list(range(0, min(n * v, target) + 1, v)) for n, v in types], {}\n",
    "        lst.sort(key = lambda x : len(x))\n",
    "        \n",
    "        def gettarget(tar, lst):\n",
    "            len_ = len(lst)\n",
    "            if len_ == 1: \n",
    "                return 1 if tar in lst[0] else 0\n",
    "            if (tar, len_) in dct: \n",
    "                return dct[(tar, len_)]\n",
    "            cnt = 0\n",
    "            for x in lst[0]:\n",
    "                if   x < tar:\n",
    "                    cnt += gettarget(tar - x, lst[1:])\n",
    "                elif x == tar:\n",
    "                    cnt += 1\n",
    "                    break\n",
    "                else:\n",
    "                    break\n",
    "            cnt %= 1000000007\n",
    "            dct[(tar, len_)] = cnt\n",
    "            return cnt\n",
    "\n",
    "        return gettarget(target, lst) \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        n = len(types)\n",
    "        mp = {}\n",
    "        \n",
    "        def dfs(tar, i):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            idx = str(i)+\"_\"+str(tar)\n",
    "            if idx in mp:\n",
    "                return mp[idx]\n",
    "            count, mark = types[i]\n",
    "            numway = 0\n",
    "            for j in range(count+1):\n",
    "                if j * mark == tar:\n",
    "                    numway += 1\n",
    "                    break\n",
    "                elif j * mark > tar:\n",
    "                    break\n",
    "                else:\n",
    "                    numway += dfs(tar-j*mark,i+1)\n",
    "            mp[idx] = numway\n",
    "            return numway\n",
    "        \n",
    "        return dfs(target,0) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def DFS(target,mark,i):\n",
    "            if mark == target:\n",
    "                return 1\n",
    "            if mark > target:\n",
    "                return 0\n",
    "            if i == len(types):\n",
    "                return 0\n",
    "            \n",
    "            return sum(DFS(target,mark + x * types[i][1],i+1) for x in range(types[i][0]+1)) %(10**9 +7)\n",
    "        \n",
    "        return sum(DFS(target,x * types[0][1],1) for x in range(types[0][0]+1))%(10**9 +7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(mask):\n",
    "            target, pos = mask//100, mask%100\n",
    "            if target == 0: return 1\n",
    "            if target < 0 or pos == len(types): return 0\n",
    "            ans = 0\n",
    "            for i in range(types[pos][0]+1):\n",
    "                ans += dfs((target-i*types[pos][1])*100 + pos+1)\n",
    "            return ans % (10**9 +7)\n",
    "\n",
    "        return dfs(target*100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i < 0: return 1 if c == 0 else 0\n",
    "            if types[i][1] > c: return dfs(i-1, c)\n",
    "            return (dfs(i-1, c) + sum(dfs(i-1, c-types[i][1] * k) % MOD for k in range(types[i][0], 0, -1))) % MOD\n",
    "\n",
    "        return dfs(len(types)-1, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        \n",
    "        MOD = 10**9+7\n",
    "\n",
    "        @functools.cache\n",
    "        def sub(i, target):\n",
    "            if target == 0:\n",
    "                return 1\n",
    "            \n",
    "            if target < 0 or i == len(types):\n",
    "                return 0\n",
    "            \n",
    "            \n",
    "            c,m = types[i]\n",
    "            return sum(sub(i+1, target-j*m) for j in range(c+1))%MOD\n",
    "\n",
    "        return sub(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def dfs(i,c):\n",
    "            if i < 0:\n",
    "                return 1 if c == 0 else 0\n",
    "            if c < types[i][1]:\n",
    "                return dfs(i-1,c) % (10**9+7)\n",
    "            return sum(dfs(i-1,c-j*types[i][1]) for j in range(types[i][0]+1)) % (10**9+7)\n",
    "        return dfs(len(types)-1,target) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, a: List[List[int]]) -> int:\n",
    "        a.sort(key=lambda x:x[1])\n",
    "        @cache\n",
    "        def back(c,pre):\n",
    "            if pre == 0:return 1\n",
    "            if c == len(a) or pre - a[c][1] < 0:return 0\n",
    "            return sum(back(c+1,pre-i*a[c][1]) for i in range(a[c][0]+1))%(10**9+7)\n",
    "        return back(0,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        big = 10**9+7\n",
    "        @cache\n",
    "        def fenshu(target, cur):\n",
    "            if target == 0: return 1\n",
    "            if target < 0: return 0\n",
    "            if target > 0 and cur == len(types): return 0\n",
    "            ans = sum([fenshu(target-i*types[cur][1], cur+1) for i in range(types[cur][0]+1)])\n",
    "            # print(target, cur, ans)\n",
    "            return ans%big\n",
    "        return fenshu(target, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        n = len(types)\n",
    "        l = [[-1] * (target + 1) for i in range(n+1)]\n",
    "        l[0][0] = 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if l[i][j] != -1:\n",
    "                return l[i][j]\n",
    "            if i == 0:\n",
    "                return 1 if j == 0 else 0\n",
    "            cnt,fen = types[i-1][0], types[i-1][1]\n",
    "            res = 0\n",
    "            for k in range(min(cnt,j // fen) + 1):\n",
    "                res += dfs(i-1,j - (k * fen))\n",
    "            l[i][j] = res\n",
    "            return res % mod\n",
    "        return dfs(n,target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        #取多重集合的一个子集，使得和为target。取这样的子集个数\n",
    "        #经典问题：找零钱\n",
    "        types.sort(key=lambda x:x[1])#按照给分升序\n",
    "        temp=[]\n",
    "        pre=0\n",
    "        for c,m in types:\n",
    "            pre+=c*m\n",
    "            temp.append(pre)\n",
    "\n",
    "        MOD=10**9+7\n",
    "        @cache\n",
    "        def dfs(i:int,curT:int):#当前下标为i，目标为target\n",
    "            if curT==0:\n",
    "                return 1\n",
    "            if i<0 or curT>temp[i]:\n",
    "                return 0\n",
    "            res=0\n",
    "            for j in range(min(curT//types[i][1],types[i][0])+1):\n",
    "                res=(res+dfs(i-1,curT-j*types[i][1]))%MOD\n",
    "            return res\n",
    "        \n",
    "        return dfs(len(types)-1,target)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        M = 10**9+7\n",
    "        n = len(types)\n",
    "        x = [0] * (n+1)\n",
    "        for i,(a,b) in enumerate(types):\n",
    "            x[i+1] = x[i] + a*b\n",
    "        \n",
    "        @cache\n",
    "        def f(i, t):\n",
    "            if i == -1:\n",
    "                return int(t == 0)\n",
    "            if t < 0 or t > x[i+1]:\n",
    "                return 0\n",
    "            if t == 0 or t == x[i+1]:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            a, b = types[i]\n",
    "            for k in range(a+1):\n",
    "                if t - k*b < 0: break\n",
    "                ans += f(i-1, t - k*b)\n",
    "            return ans % M\n",
    "        \n",
    "        return f(n-1, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def dp(i, target):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            \n",
    "            cnt, mark = types[i]\n",
    "            \n",
    "            if i == 0:\n",
    "                if target % mark == 0 and target <= cnt * mark:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            \n",
    "            res = dp(i-1, target)\n",
    "            for c in range(1, cnt+1):\n",
    "                if target -c * mark < 0:\n",
    "                    break\n",
    "                res += dp(i-1, target - c * mark)\n",
    "            return res % mod\n",
    "            \n",
    "        \n",
    "        n = len(types)\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        return dp(n-1, target) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(types)\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i < 0:\n",
    "                return 1 if c == 0 else 0\n",
    "            count, marks = types[i]\n",
    "            res = 0\n",
    "            res += dfs(i - 1, c)\n",
    "            for k in range(1, min(count, c // marks) + 1):\n",
    "                res += dfs(i - 1, c - k * marks)\n",
    "            return res % MOD\n",
    "        return dfs(n - 1, target)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, target):\n",
    "            if i == l:\n",
    "                return 1 if target == 0 else 0\n",
    "            res = dfs(i + 1, target)\n",
    "            c, m = types[i]\n",
    "            while c > 0 and target - m >= 0:\n",
    "                target -= m\n",
    "                c -= 1\n",
    "                res += dfs(i + 1, target)\n",
    "                res %= mod\n",
    "            return res\n",
    "        l = len(types)\n",
    "        mod = 10 ** 9 + 7\n",
    "        return dfs(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        n = len(types)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i: int, cur: int) -> int:\n",
    "            if i == n:\n",
    "                return cur == target\n",
    "            \n",
    "            res = 0\n",
    "            for cnt in range(1, types[i][0] + 1):\n",
    "                if cur + cnt * types[i][1] <= target:\n",
    "                    res = (res + dfs(i + 1, cur + cnt * types[i][1])) % MOD\n",
    "            res = (res + dfs(i + 1, cur)) % MOD\n",
    "            return res\n",
    "\n",
    "        return dfs(0, 0) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        MOD = 10**9 +  7\n",
    "        @cache\n",
    "        def dfs(i, k):\n",
    "            if k < 0:\n",
    "                return 0\n",
    "            if i == 0:\n",
    "                return 1 if k // types[i][1] <= types[i][0] and k % types[i][1] == 0 else 0\n",
    "            ans = 0\n",
    "            for j in range(min(k // types[i][1]+1,types[i][0]+1 )):\n",
    "                ans += dfs(i-1, k - j * types[i][1])\n",
    "            return ans % MOD\n",
    "        return dfs(len(types)-1, target)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            \"\"\"\n",
    "            i:代表前i种题目\n",
    "            j:目标分数\n",
    "            \"\"\"\n",
    "            if i < 0:\n",
    "                return 1 if j == 0 else 0\n",
    "            count, mark = types[i]\n",
    "            # j - mark * k >= 0\n",
    "            # k <= j // mark\n",
    "            res = 0\n",
    "            for k in range(min(count, j // mark) + 1):\n",
    "                res += dfs(i - 1, j - k * mark)\n",
    "            return res % MOD\n",
    "\n",
    "        return dfs(len(types) - 1, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(types)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i < 0:\n",
    "                return 1 if j == 0 else 0\n",
    "            ans = 0\n",
    "            cnt, mask = types[i]\n",
    "            for k in range(min(cnt, j // mask) + 1):\n",
    "                ans += dfs(i - 1, j - mask * k) % MOD\n",
    "            return ans % MOD\n",
    "        return dfs(n - 1, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, x: int, p: List[List[int]]) -> int:\n",
    "        mod=10**9+7\n",
    "        n=len(p)\n",
    "        @cache\n",
    "        def dfs(c,i):\n",
    "            if c==x:\n",
    "                return 1\n",
    "            if i==n:\n",
    "                return 0\n",
    "            ans=0\n",
    "            for j in range(p[i][0]+1):\n",
    "                if c+p[i][1]*j<=x:\n",
    "                    ans=(ans+dfs(c+p[i][1]*j,i+1))%mod\n",
    "            return ans\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        n = len(types)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, x):\n",
    "            if i == n or x == 0:\n",
    "                return int(x == 0)\n",
    "            \n",
    "            c, m = types[i]\n",
    "            ans = 0\n",
    "            for j in range(c + 1):\n",
    "                if x >= j * m:\n",
    "                    ans += dfs(i + 1, x - j * m)\n",
    "                    ans %= 10**9 + 7\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0, target)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:\n",
    "        n = len(types)\n",
    "        @cache\n",
    "        def fun(now, grade):\n",
    "            if n == now:\n",
    "                return grade == target\n",
    "            res = 0\n",
    "            for i in range(types[now][0]+1):\n",
    "                if grade + types[now][1]*i <= target:\n",
    "                    res += fun(now+1, grade + types[now][1]*i)\n",
    "                else:\n",
    "                    break\n",
    "            return res\n",
    "        return fun(0, 0) % (10**9 + 7)\n",
    "        '''\n",
    "        dp = [[0]*target + [1] for _ in range(n+1)]\n",
    "        for now in range(n-1, -1, -1):\n",
    "            for grade in range(target-1, -1, -1):\n",
    "                for i in range(types[now][0]+1):\n",
    "                    if grade + types[now][1]*i <= target:\n",
    "                        dp[now][grade] += dp[now+1][grade + types[now][1]*i]\n",
    "                    else:\n",
    "                        continue\n",
    "        return dp[0][0] % (10 ** 9 + 7)\n",
    "        '''\n",
    "        '''\n",
    "        @cache\n",
    "        def fun(now, grade):\n",
    "            if n == now:\n",
    "                return grade == target\n",
    "            res = 0\n",
    "            for i in range(types[now][0]+1):\n",
    "                if grade + types[now][1]*i <= target:\n",
    "                    res += fun(now+1, grade + types[now][1]*i)\n",
    "                else:\n",
    "                    break\n",
    "            return res\n",
    "        return fun(0, 0) % (10**9 + 7)\n",
    "        '''"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
